ЗАДАЧА 3.A. Провести анализ и составить платежные матрицы следующих игр:

Вариант 7.

            “Волк, коза, капуста”. Игроки одновременно называют одно из этих слов, причем «волк » побеждает «козу», «коза» – «капусту», а «капуста» -«волка». Игрок, который назовет выигрывающее слово, выигрывает у противника одну единицу; если оба игрока выберут одинаковые слова, игра оканчивается вничью.

 

“Волк, коза, капуста”. Игроки одновременно называют одно из этих слов, причем «волк » побеждает «козу», «коза» – «капусту», а «капуста» -«волка». Игрок, который назовет выигрывающее слово, выигрывает у противника одну единицу; если оба игрока выберут одинаковые слова, игра оканчивается вничью.

Внимание!

Это ОЗНАКОМИТЕЛЬНАЯ ВЕРСИЯ работы №2075, цена оригинала 200 рублей. Оформлена в программе Microsoft Word.

Оплата. Контакты.

Решение:

Игра состоит из двух личных ходов. У игрока А три возможны стратегии: А1 — игрок А называет «волк»; А2 — игрок А называет «коза»;  А3 — игрок А называет «капуста». Аналогично у игрока В: В1 — игрок В называет «волк»; В2 — называет «коза»; В3 — игрок В А называет «капуста».

Возможны следующие ситуации:

А1-В1. Оба игрока называют «волк» , выигрыши игроков равны 0;

А1-В2. Игрок А называет «волк», игрок В – «коза». Выигрыш игрока А равен 1;

А1-В3. Игрок А называет «волк», игрок В — «капуста». Выигрыш игрока А равен -1;

А2-В1. Игрок А называет «коза», игрок В — называет «волк». Выигрыш игрока А равен -1;

А2-В2. Оба игрока называют «коза»,  выигрыши игроков равны 0;

А2-В3. Игрок А называет «коза», игрок В — называет «капуста». Выигрыш игрока А равен -1

А3-В1. Игрок А называет «капуста», игрок В — называет «волк». Выигрыш игрока А равен 1;

А3-В2. Игрок А называет «капуста», игрок В — называет «коза». Выигрыш игрока А равен — 1;

А3-В3. Оба игрока называют «капуста»,  выигрыши игроков равны 0;

 

Игра представляет собой игру 3´3 с матрицей, приведенной в таблице:

        Таблица

 

 

Вариант 8.

В игре двух игроков А и В участвуют восемь карт: четыре «туза» и четыре «шестерки». Игроки берут по две карты и выкладывают их на стол. Игрок, выложивший большую карту, выигрывает 1 рубль, другой игрок, соответственно, этот рубль проигрывает. Если игроки выкладывают одинаковые карты, то никто из игроков не выигрывает

Решение

Игра состоит из двух случайных ходов (раздача карт) и двух личных ходов — выкладывание карт на стол. У игрока А возможны следующие случайные ходы: А1 — игрок А берет 2 тузов; А2 — игрок А берет туза и «шестерку»; А3 — игрок А берет две «шестерки». Аналогично у игрока В: В1 — игрок В берет 2 тузов; В2 — игрок В берет туза и «шестерку»; В3 — игрок В берет две «шестерки».

Возможны следующие ситуации:

А1-В1. Оба игрока берут по два туза, «выигрыши» игроков равны 0;

А1-В2. Игрок А взял два туза, игрок В — туз + «шестерку». Выигрыш игрока А равен 1;

А1-В3. Игрок А взял два туза, игрок В — две «шестерки». Выигрыш игрока А равен 2;

А2-В1. Игрок А взял туз + «шестерку», игрок В — два туза. Выигрыш игрока А равен -1;

А2-В2. Оба игрока взяли туза + «шестерку», выигрыши игроков равны 0;

А2-В3. Игрок А взял туза + «шестерку», игрок В — две «шестерки». Выигрыш игрока А равен 1;

А3-В1. Игрок А взял две «шестерки», игрок В — двух тузов, выигрыш игрока А равен -2;

А3-В2. Игрок А взял две «шестерки», игрок В — туза + «шестерку», выигрыш игрока А равен -1;

А3-В3. Оба игрока взяли по две «шестерки», выигрыши игроков равны 0.

Игра представляет собой игру 3´3 с матрицей, приведенной в таблице:

        Таблица

 

Вариант 10.

Игрок А записывает одно из двух чисел: 1 или 2, игрок В — одно из трех чисел: 1, 2 или 3.Если сумма написанных чисел четная, то игрок В платит игроку А эту сумму в рублях; если она нечетная, то, наоборот, игрок А платит игроку В эту сумму.

Решение:

Игра состоит из двух ходов; оба — личные. У нас (А) две стратегии: А1 — писать 1; А2 — писать 2. У противника (В)- три стратегии. Возможны следующие ситуации:

А1-В1. Оба игрока написали «1», выигрыш игрока А равен 2.

А1-В2. Игрок А написал «1», игрок В — «2». Выигрыш игрока А равен -3.

А1-В3. Игрок А написал «1», игрок В — «3». Выигрыш игрока А равен 4.

А2-В1. Игрок А написал «2», игрок В — «1». Выигрыш игрока А равен -3.

А2-В2. Игрок А написал «2», игрок В — «2». Выигрыш игрока А равен 4.

А2-В3. Игрок А написал «2», игрок В — «3». Выигрыш игрока А равен -5.

Игра представляет собой игру 2´3 с матрицей, приведенной в таблице:

Таблица 1.                                                           Таблица 2.

B A	B1	B2	B3		B A	B1	B2
A1	2	-3	4		A1	(0,0)	(-5,5)
А2	-3	4	-5		А2	(5,-5)	(-100,100)

 

 

    ЗАДАЧА 3.С. Решение конечной матричной игры в смешанных

                                    стратегиях  графоаналитическим методом;

Вариант 7.

	В1	В2
А1	2	0
А2	1	3
А3	0	2
А4	-1	4
А5	-2	2

 

Решение:

Убеждаемся, прежде всего, в том, что в игровой матрице нет седловых точек.  Для этого вычислим нижнюю и верхнюю цену игры:

a  = max min a _ij = max (0; 1; 0; -1; -2) = 1,

i          j                   i

b  = min max  a _ij = min (2;  4) = 2.

j     i                 j

и приходим к выводу, что  a  ¹ b .  Следовательно, решение игры следует искать в области смешанных стратегий.

Имеем игру размера mx2, поэтому построим графики функции выигрыша 2-го игрока в зависимости от вероятностей применения его чистых стратегий при различных стратегиях 1-го игрока (рис.1).

Выделим  жирной ломаной линией А₁NMA₂ верхнюю границу выигрышей – максимальный проигрыш игрока В. точка N, в которой этот максимальный проигрыш достигает наименьшего значения  определяет решение игры и цену игры.

В точке N пересекаются  стратегии  А₁ и А₂, которые являются  активными  стратегиями 1-го  игрока.

Из графика видно, что  А₃ и А₅  являются заведомо невыгодными стратегиями игрока А, а стратегия А₄ – невыгодной при оптимальной стратегии S_В^*.

Если игрок В будет придерживаться своей оптимальной смешанной стратегии S_В^*, то выигрыш не изменится, какой бы из своих активных стратегий не пользовался игрок А. Однако, он изменится, если игрок А перейдет к стратегиям А₃, А₄, А₅.

Согласно теореме об активных стратегиях,  составим системы уравнений:

а) для игрока А:    2×р₁ + 1×р₂ = n;

0×p₁ + 3×p₂ = n;

p₁ + p₂ = 1 – как сумма вероятностей достоверных событий.

Из (1) и (2) имеем    2×p₁ + p₂ = 3×p₂

из (3)   p₁ = 1 — p₂

то есть        2× (1 — p₂ ) + p₂ = 3×p₂    отсюда    4×p₂ = 2  и p₂ = 1/2

далее p₁ = 1/2    и    n = 3×р₂ = 3/2 = 1,5.

То есть       p₁ = 0,5;     p₂ = 0,5;     n = 1,5.

б) для игрока В:             2×q₁ + 0×q₂ =   n = 1,5;

q₁ + q₂ =  1.

Решив эту систему, получим

q₁ = 0,75;       q₂ = 0,25

Таким образом, оптимальными стратегиями сторон будут

S_А*= (0,75;  0,25;  0;  0;  0;) S_b* =(0,5;   0,5)   

                 средний выигрыш      n = 1,5.

 

 

Вариант 8.      Имеется  игра  с матрицей 

1    5    3    2	В1	В2
А1	1	0
А2	3	1
(B2)    (B1)    А3	-2	3
-1    А4	0	-4
А5	5	-3
-2    А6	0,5	2

 

Решение:

Убеждаемся, прежде всего, в том, что в игровой матрице нет седловых точек. Для этого вычислим нижнюю и верхнюю цены  игры

a = max min a _ij = max (0; 1; -2; -4; -3; 0,5) = 1,

i       j                i

b = min max  a _{ij  =} min (5; 3) = 3

j       i               j

и приходим к выводу, что   a  ¹ b.  Следовательно, игра не имеет седловой точки и решение следует искать в области смешанных стратегий.

Строим графики функций выигрышей. Так как данная игра размера 6 х 2, строим графики функции  выигрышей 2-го игрока в зависимости от вероятностей применения им своих чистых стратегий при различных стратегиях 1-го игрока (рис. 4с.3). Как видно из рисунка, стратегии А₁ и А₄ заведомо невыгодные.

Выделим  жирной   линией  верхнюю   границу   выигрышей  — ломаную           — MLNP — максимальные проигрыши игрока В. Находим точку N, в которой эти максимальные проигрыши достигают наименьшего значения.

В точке N пересекаются линии стратегий А₂, А₃ и А₆, которые являются активными стратегиями игрока А. Из этих стратегий сторона А может выбрать любые две  с противоположным наклоном, например, А₂, А₃ или А₂, А₆ (выбор А₃, А₆ исключен, так как они имеет одинаковые наклоны, что приведет к решению игры в чистых стратегиях).

Выберем   стратегии А₂ и А₃.   Тогда  для  игры  2 х 2  (стратегии А₂,А₃  и  В₁, В₂) составим систему уравнений согласно теореме об активных стратегиях.

а) для стороны А:      3×p₂ — 2×p₃ = n;

p₂ + 3×p₃ = n;

p₂ + p₃ = 1.

Из (3)     p₂ = 1 — p₃

из (1)    3× (1 — p₃) — 2×p₃ = n      Þ     3 — 5×p₃ = n

из (2)    1 — p₃ + 3×p₃ = n      Þ     1 + 2×p₃ = n

далее 3 — 5×p₃ = 1 + 2×p₃   Þ     7×p₃ = 2;

Отсюда p₃ = 2/ 7;     p₂ = 5/ 7;      n = 11/ 7.

б) для стороны В:  3×q₁ +   q₂ = 11/ 7;

-2×q₁ + 3×q₂ = 11/ 7.

Из (1)      q₂ = 11/ 7 — 3×q₁

из (2)   -2×q₁ + 3× (11/ 7 — 3×q₁) = 11/ 7

-2×q₁ — 9×q₁ = 11/ 7 — 33/ 7

11×q₁ = -22/ 7

Отсюда  q₁ = 2/ 7;   q₂ = 5/ 7;

Таким образом, оптимальными стратегиями сторон являются:

                   S_a* = (0;  5/ 7;  2/ 7;  0;  0;  0)

S_b* = (2/ 7;    5/ 7)                  при значении выигрыша    n = 11/ 7.

Теперь выберем стратегии А₂ и А₆. Решив соответствующие системы

уравнений, получим    p₂ = 3/ 7;       p₆ = 4/ 7;        n = 11/ 7

q₁ = 2/ 7;       q₂ = 5/ 7.

S_a* = (0;  3/ 7;  0;  0;  0;  4/ 7)

S_b* = (2/ 7;   5/ 7)

     при том же значении выигрыша    n = 11/ 7.

 

Вариант 10.

Имеется игра с матрицей

 

	В1	В2	В3	В4	В5
А1	-1	3	-2	5	1/2
А2	0	1	3	-3	2

 

Решение:
         Проверим,  прежде всего,  наличие в данной игре  седловых точек.  Для этого вычислим нижнюю и верхнюю цены игры:

a = max min a _ij = max (-2, -3) = -2,

i        j

b = min max  a _ij = min  (0, 3, 3, 5, 2) = 0

j        i

и  приходим  к выводу: a ¹ b.  Следовательно, игра не имеет седловой точки и решение следует искать в области смешанных стратегий.

Построим графики функции выигрыша 1-го игрока в зависимости от вероятностей применения его чистых стратегий при различных стратегиях 2-го игрока (рис.).  Стратегия В₁   дает  на осях  I-I  и II-II, соответственно,  две точки с ординатами  a₁₁= -1  и  a₂₁ = 0.  Соединим эти точки  прямой B₁.  Стратегия В₂ дает точки  с  ординатами  a₁₂ = 3, a₂₂ = 1.  Соединим прямой В₂.   Аналогично, строим графики   стратегий  В₃, В₄, В₅.

Из графика видно, что  В₂ и В₅  являются заведомо невыгодными стратегиями 2-го игрока.

Выделим жирной ломаной линией MLNP нижнюю границу  выигрышей —  минимальный  выигрыш  игрока  А. Точка N,  в которой этот минимальный выигрыш   достигает   наибольшего  значения,  определяет решение и цену игры.  В точке  N  пересекаются  стратегии  В₁ и В₄, которые являются  активными  стратегиями 2-го  игрока. Имея в виду теорему об активных стратегиях,  составим системы уравнений.

а) для игрока А:              -р₁ — 0×р₂ = n;

5×p₁ — 3×p₂ = n;

p₁ + p₂ = 1.

Решаем эту систему:       из (3)     p₁ = 1 — p₂;

из (2)  5×p₁ — 3 + 3×p₁ = n   Þ    8×p₁ — 3 = n

из (1)    -p₁ = n      поэтому    8×p₁  — 3 = — p₁

Отсюда           p₁ = 1/3;           p₂ = 2/3 ;            n =  -1/3

 

б) для игрока В:              -q₁  + 5×q₄ = n =   -1/3;

0×q₁  —  3×q₄ =  n =  -1/3;

Решаем эту систему: из (2) q₄ = n/3 = 0,11;

из (1)  q₁ = 5×q₄ — n = 5×0,11 — (-0,33) = 0,89.

То есть,  q₁ = 8/9;           q₄ = 1/9;

Таким образом, оптимальными стратегиями сторон будут

S_a*= (1/3; 2/3)                        S_b* = (8/9; 0; 0; 1/9; 0;)

                 средний выигрыш    n = -1/3.

 

ЗАДАЧА 3.В.  Решение конечной игры в чистых стратегиях методом минимакса с помощью седловой точки

*****************

Для игр с приведенными платежными матрицами определить:

— нижнюю и верхнюю цены игры;

— минимаксные стратегии;

— оптимальные решения игры в чистых стратегиях с помощью седловой точки.

***************** Вариант 7.            4   5   6   7   9 3   4   6   5   6 7   6  10   8  11 8   5   4   7   3 Запишем матрицу игры в виде таблицы: В1 В2 B3 B4 В5 ai   Проанализируем ситуацию. Какую бы стратегию не выбрал игрок А, его  противник В выберет такую  стратегию, чтобы минимизировать свой проигрыш. Так как W2 = -W1, то игрок В, тем самым, старается минимизировать выигрыш игрока А, т.е. чтобы  выигрыш игрока А был равен A1 4 5 6 7 9 4   A2 3 4 6 5 6 3   A3 7 6 10 8 11 6   A4 8 5 4 7 3 3   bj 8 6 10 8 11 a=6 b=6   Определим  ai для каждой стратегии игрока А. В ответ игрок А выберет свою стратегию таким образом, чтобы в этой cитуации максимизировать свой минимальный выигрыш, т.е. а32 = 6. a = 6 есть нижняя цена игры, она достигается при стратегии А3, которая является максиминной стратегией игрока А. С другой  стороны, какую бы  стратегию не выбрал  игрок В, игрок А выберет свою такую стратегию, чтобы максимизировать свой выигрыш и, тем самым максимизировать проигрыш игрока В, т.е. . Определим  для каждой стратегии игрока В. В ответ игрок В выберет свою стратегию таким образом, чтобы в этой ситуации минимизировать свой проигрыш, т.е. а32 = 6 b = 6 есть верхняя цена игры, она достигается при стратегии В3, которая является минимаксной стратегией игрока В. В данной игре a=b= a32 = 6, т.е. игра имеет седловую точку, в которой оба  игрока  получают   свои  гарантированные   выигрыши,  равные  цене игры V = a= b = 6. Стратегии А3 и В2 являются оптимальными стратегиями. Вариант 8.            2     5     3     3 6     8     5     7 3     5     4     4 2     3     4     4 Запишем матрицу игры в виде таблицы:   В1 В2 В3 B4 ai   Проанализируем ситуацию. Какую бы стратегию не выбрал игрок А, его  противник В выберет такую  стратегию, чтобы минимизировать свой проигрыш. Так как W2 = -W1, то игрок В, тем самым, старается минимизировать выигрыш игрока А, т.е. чтобы  выигрыш игрока А был равен A1 2 5 3 3 2   A2 6 8 5 7 5   A3 3 5 4 4 3   A4 2 3 4 4 2   bj 6 8 5 5 a=5 b=5   Определим  ai для каждой стратегии игрока А. В ответ игрок А выберет свою стратегию таким образом, чтобы в этой cитуации максимизировать свой минимальный выигрыш, т.е. a23 = 5. a = 5 есть нижняя цена игры, она достигается при стратегии А2, которая является максиминной стратегией игрока А. С другой  стороны, какую бы  стратегию не выбрал  игрок В, игрок А выберет свою такую стратегию, чтобы максимизировать свой выигрыш и, тем самым максимизировать проигрыш игрока В, т.е. . Определим  для каждой стратегии игрока В. В ответ игрок В выберет свою стратегию таким образом, чтобы в этой ситуации минимизировать свой проигрыш, т.е. a23 = 5. b = 5 есть верхняя цена игры, она достигается при стратегии В3, которая является минимаксной стратегией игрока В. В данной игре a=b= a23 = 5, т.е. игра имеет седловую точку, в которой оба  игрока  получают   свои  гарантированные   выигрыши,  равные  цене игры V = a= b = 5. Стратегии А2 и В3 являются оптимальными стратегиями.   Вариант 10.            4     5    3     6 6     7     4    5 5     2     3    4

Запишем матрицу игры в виде таблицы:

	В1	В2	В3	B4	ai
A1	4	5	3	6	3
A2	6	7		5	4
A3	5	2	3	4	2
bj	6	7	4	6	α = 4 β = 4

 

 

Проанализируем ситуацию.

Какую бы стратегию не выбрал игрок А, его  противник В выберет такую  стратегию, чтобы минимизировать свой проигрыш. Так как W₂ = — W₁, то игрок В, тем самым, старается минимизировать выигрыш игрока А, т.е. чтобы  выигрыш игрока А был равен

Определим  a_i для каждой стратегии игрока А.

В ответ игрок А выберет свою стратегию таким образом, чтобы в этой cитуации максимизировать свой минимальный выигрыш, т.е.

a₂₃ = 4.

a = 4 есть нижняя цена игры, она достигается при стратегии А₂, которая является максиминной стратегией игрока А.

С другой  стороны, какую бы  стратегию не выбрал  игрок В, игрок А выберет свою такую стратегию, чтобы максимизировать свой выигрыш и, тем самым максимизировать проигрыш игрока В, т.е. .

Определим  для каждой стратегии игрока В.

В ответ игрок В выберет свою стратегию таким образом, чтобы в этой ситуации минимизировать свой проигрыш, т.е.

a₂₃ = 4.

b = 4 есть верхняя цена игры, она достигается при стратегии В₃, которая является минимаксной стратегией игрока В.

В данной игре a=b= a₂₃ = 4, т.е. игра имеет седловую точку, в которой оба  игрока  получают   свои  гарантированные   выигрыши,  равные  цене игры

V = a= b = 4.

Стратегии А₂ и В₃ являются оптимальными стратегиями.

 

 

 

  ЗАДАЧА 3.D. Приведение конечной матричной игры к задачам линейного программирования;

***************** 

 Для игры, заданной платежной матрицей (таблицей) :

а) убедиться в отсутствии решения в чистых стратегиях;

б) обосновать необходимость решения игры путем приведения ее к задаче ЛП;

в) сформулировать для игроков соответствующие задачи линейного программирования (составить целевые функции, системы ограничительных условий), провести анализ полученных задач ЛП на двойственность.

Вариант 7.

	В1	В2	В3	В4
А1	0,8	0,2	0,4	0,2
А2	0,4	0,5	0,6	0,5
А3	0,1	0,7	0,3	0,1
А4	0,8	0,7	0,6	0,1

 

Решение:

Чтобы не иметь  дела с дробями,  умножим все элементы матрицы на 10; при этом  цена игры увеличится в 10 раз, а решение не изменится.  Получим матрицу:

	В1	В2	В3	В4
А1	8	2	4	2
А2	4	5	6	5
А3	1	7	3	1
А4	8	7	6	1

 

Проверим наличие седловой точки в данной игре:

a = a_ij= max (2;  4;  1;  1) = 4;

b = a_ij= min (8;  7;  6;  5) = 5.

Видим, что a¹b,  то есть, игра не имеет седловой точки, следовательно ее решение ищем в области смешанных  стратегий.  Так как игра имеет  размерность 4х4, для решения  сведем ее к задаче линейного программирования.

На основании теоремы об активных стратегиях запишем уравнения для определения оптимальной стратегии игрока А:

8·p₁ + 4·p₂ +   p₃ + 8·p₄  ³ n   — при В₁;

2·p₁ + 5·p₂ + 7·p₃ + 7·p₄ ³ n   — при В₂;

4·p₁ + 6·р₂ + 3·p₃ + 6·p₄ ³ n   — при В₃;

2·p₁ + 5·р₂ +    p₃ +    p₄ ³ n   — при В₄;

р₁ + р₂ + р₃ + p₄ = 1.

Разделив обе части уравнений на n > 0 и обозначив G_i= pi/ n, получим

8·G₁ + 4·G₂ +   G₃ + 8·G₄  ³  1;

2·G₁ + 5·G₂ + 7·G₃ + 7·G₄  ³  1;                (3.1)

4·G₁ + 6·G₂ + 3·G₃ + 6·G₄  ³  1;

2·G₁ + 5·G₂ +    G₃ +    G₄  ³  1;

G₁ + G₂ + G₃ + G₄ = 1/ n,

Решение  игры  должно  максимизировать  значение  n,  значит, функция  Ф = 1/ n = G₁ + G₂ + G₃ + G₄ должна принимать минимальное значение. То есть, имеем задачу линейного программирования

    найти значения переменных G_i ³ 0,   i = 1, 4,  обеспечивающие минимум  линейной  функции  Ф = 1/n = G₁ + G₂ + G₃ + G₄   при ограничениях   (3.1)   и условии неотрицательности переменных G_i

 

Для определения оптимальной  стратегии игрока В составим систему уравнений:                            8·q₁ + 2·q₂ + 4·q₃ + 2·q₄ £ n    — при А₁;

4·q₁ + 5·q₂ + 6·q₃ + 5·q₄ £ n    — при А₂;

q₁ + 7·q₂ + 3·q₃ +    q₄ £ n    — при А₃;

8·q₁ + 7·q₂ + 6·q₃ +    q₄ £ n    — при А₄;

q₁ + q₂ + q₃ + q₄ = 1.

Разделив обе части уравнений на n > 0, и обозначив U_j =1/n, получим

8·U₁ + 2·U₂ + 4·U₃  + 2·U₄  £ 1;

4·U₁ + 5·U₂  + 6·U₃ + 5·U₄ £ 1;

U₁ + 7·U₂  + 3·U₃ +   U₄ £ 1;          (3.2)

8·U₁ + 7·U₂ + 6·U₃ +   U₄ £ 1;

U₁ + U₂ + U₃ + U₄ = 1/n

и учитывая,  что  решение игры должно минимизировать n,  следовательно максимизировать 1/n, получим задачу линейного программирования для определения оптимальной стратегии игрока В,  которая является двойственной  к  задаче определения оптимальной стратегии игрока А и формулируется так:

 найти значения переменных Uj ³ 0,   i = 1, 4,  обеспечивающие максимум  линейной  функции  F = 1/n = U₁ + U₂ + U₃ +U₄   при ограничениях   (3.2)   и условии неотрицательности переменных G_i

Введя дополнительные неотрицательные переменные z₁, z₂, z₃, z₄  неравенства преобразуем   в уравнения, затем  решим полученную задачу линейного программирования с помощью симплексного метода.

 

Вариант 8.                                  4   3   4   2

А =            3   4   6   5

2   5   1   3

5   3   6  11

Решение:

Сначала проверим наличие седловой точки в данной игре:

a = a_ij= max (2; 3; 1; 3) = 3

b = a_ij= min (5; 5; 6; 11) = 4.

Видим, что a¹b,  то есть, игра  не имеет седловой точки, следовательно ее решение ищем в области смешанных  стратегий.  Так как игра имеет  размерность 4х4, для ее  решения  применим  симплексный метод.   С этой  целью сведем игру к задаче линейного программирования.

Для  определения  оптимальной  стратегии  игрока А  согласно теореме об активных стратегиях составим  следующую систему уравнений:

4·р₁ + 3·р₂ + 2·р₃  +  5·р₄ ³ n      — при В₁;

3·р₁ + 4·р₂ + 5·р₃  +  3·р₄ ³ n      — при В₂

4·р₁ + 6·р₂ +    р₃  +  6·р₄ ³ n      — при В₃;

2·р₁ + 5·р₂ + 3·р₃  + 11·р₄ ³ n     — при В₄;

р₁ + р₂ + р₃ +  р₄ = 1,                — как сумма вероятностей

р_i ³ 0,       i = 1, 4           достоверных событий.

Разделив обе части неравенств и уравнения на  n ³ 0 и обозначив G_i = p_i/ n,  получим              4·G₁ + 3·G₂ + 2·G₃   +  5·G₄ ³ 1;

3·G₁ + 4·G₂ + 5·G₃   + 3·G₄ ³ 1;

4·G₁ + 6·G₂ +    G₃   +  6·G₄ ³ 1;              (1.1)

2·G₁ + 5·G₂ + 3·G₃   + 11·G₄³ 1;

G₁ + G₂ + G₃ + G₄ = 1/ n.

Решение игры для игрока А должно максимизировать значение n, значит, функция Ф = 1/n = G₁ + G₂ + G₃ +  G₄ должна принимать минимальное значение. То есть, имеем задачу линейного программирования :

 найти значения переменных G_i ³ 0,   i = 1, 4,  обеспечивающие минимум  линейной  функции  Ф = G₁ + G₂ + G₃ + G₄   при ограничениях   (1.1)   и условии неотрицательности переменных G_i

Для определения оптимальной  стратегии игрока В составим систему

уравнений:                   4·q₁ + 3·q₂ + 4·q₃ +  2·q₄  £ n — при А₁;

3·q₁ + 4·q₂ + 6·q₃ +  5·q₄  £ n  — при А₂;

2·q₁ + 5·q₂ +    q₃ +  3·q₄  £ n  — при А₃;

5·q₁ + 3·q₂ + 6·q₃ +11·q₄  £ n  — при А₄;

q₁ + q₂ + q₃ + q₄= 1;                q_j ³ 0,   ( j = 1, 4 )

Разделив обе части  уравнений на n > 0 и обозначив U_j = q_j/ n,  получим                                     4·U₁ + 3·U₂ + 4·U₃  +  2·U₄ £ 1,

3·U₁ + 4·U₂ + 6·U₃  +  5·U₄ £ 1,                          (1.2)

2·U₁ + 5·U₂ +    U₃  +  3·U₄ £ 1,

5·U₁ + 3·U₂ + 6·U₃ + 11·U₄ £ 1,

U₁ + U₂ + U₃ + U₄ = 1/ n.

Так как решение игры для игрока В должно минимизировать n, следовательно максимизировать 1/ n, получим задачу линейного программирования:

найти значения переменных U_j ³ 0,   j = 1, 4,  обеспечивающие максимум  линейной  функции  F = 1/ n = U₁ + U₂ + U₃ + U₄   при ограничениях   (1.2)   и условии неотрицательности переменных G_i

Данная задача  является двойственной  к задаче  определения оптимальной стратегии игрока А. Введя дополнительные неотрицательные  переменные  z₁, z₂, z₃, z₄   приведем ее к каноническому виду, затем решим  полученную задачу линейного программирования с помощью симплексного метода.

 

Вариант 10.

	В1	В2	В3	В4
А1	0,8	0,2	0,4	0,2
А2	0,4	0,5	0,6	0,5
А3	0,1	0,7	0,3	0,1
А4	0,8	0,7	0,6	0,1

 

 

Решение:

Чтобы не иметь  дела с дробями,  умножим все элементы матрицы на 10; при этом  цена игры увеличится в 10 раз, а решение не изменится.  Получим матрицу:

	В1	В2	В3	В4
А1	8	2	4	2
А2	4	5	6	5
А3	1	7	3	1
А4	8	7	6	1

 

Проверим наличие седловой точки в данной игре:

a = a_ij= max (2;  4;  1;  1) = 4;

b = a_ij= min (8;  7;  6;  5) = 5.

Видим, что a¹b,  то есть, игра не имеет седловой точки, следовательно ее решение ищем в области смешанных  стратегий.  Так как игра имеет  размерность 4х4, для решения  сведем ее к задаче линейного программирования.

На основании теоремы об активных стратегиях запишем уравнения для определения оптимальной стратегии игрока А:

8·p₁ + 4·p₂ +   p₃ + 8·p₄  ³ n   — при В₁;

2·p₁ + 5·p₂ + 7·p₃ + 7·p₄ ³ n   — при В₂;

4·p₁ + 6·р₂ + 3·p₃ + 6·p₄ ³ n   — при В₃;

2·p₁ + 5·р₂ +    p₃ +    p₄ ³ n   — при В₄;

р₁ + р₂ + р₃ + p₄ = 1.

Разделив обе части уравнений на n > 0 и обозначив G_i= pi/ n, получим

8·G₁ + 4·G₂ +   G₃ + 8·G₄  ³  1;

2·G₁ + 5·G₂ + 7·G₃ + 7·G₄  ³  1;                (3.1)

4·G₁ + 6·G₂ + 3·G₃ + 6·G₄  ³  1;

2·G₁ + 5·G₂ +    G₃ +    G₄  ³  1;

G₁ + G₂ + G₃ + G₄ = 1/ n,

Решение  игры  должно  максимизировать  значение  n,  значит, функция  Ф = 1/ n = G₁ + G₂ + G₃ + G₄ должна принимать минимальное значение. То есть, имеем задачу линейного программирования

    найти значения переменных G_i ³ 0,   i = 1, 4,  обеспечивающие минимум  линейной  функции  Ф = 1/n = G₁ + G₂ + G₃ + G₄   при ограничениях   (3.1)   и условии неотрицательности переменных G_i

 

Для определения оптимальной  стратегии игрока В составим систему уравнений:                            8·q₁ + 2·q₂ + 4·q₃ + 2·q₄ £ n    — при А₁;

4·q₁ + 5·q₂ + 6·q₃ + 5·q₄ £ n    — при А₂;

q₁ + 7·q₂ + 3·q₃ +    q₄ £ n    — при А₃;

8·q₁ + 7·q₂ + 6·q₃ +    q₄ £ n    — при А₄;

q₁ + q₂ + q₃ + q₄ = 1.

Разделив обе части уравнений на n > 0, и обозначив U_j =1/n, получим

8·U₁ + 2·U₂ + 4·U₃  + 2·U₄  £ 1;

4·U₁ + 5·U₂  + 6·U₃ + 5·U₄ £ 1;

U₁ + 7·U₂  + 3·U₃ +   U₄ £ 1;          (3.2)

8·U₁ + 7·U₂ + 6·U₃ +   U₄ £ 1;

U₁ + U₂ + U₃ + U₄ = 1/n

и учитывая,  что  решение игры должно минимизировать n,  следовательно максимизировать 1/n, получим задачу линейного программирования для определения оптимальной стратегии игрока В,  которая является двойственной  к  задаче определения оптимальной стратегии игрока А и формулируется так:

 найти значения переменных Uj ³ 0,   i = 1, 4,  обеспечивающие максимум  линейной  функции  F = 1/n = U₁ + U₂ + U₃ +U₄   при ограничениях   (3.2)   и условии неотрицательности переменных G_i

Введя дополнительные неотрицательные переменные z₁, z₂, z₃, z₄  неравенства преобразуем   в уравнения, затем  решим полученную задачу линейного программирования с помощью симплексного метода.